package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 1/12/21 11:20 AM
 */
public class _148_排序链表_归并排序 {


    public ListNode sortList(ListNode head) {

        if (head == null || head.next == null) {

            return head;
        }

        return divide(head,null);
    }


    private ListNode divide(ListNode head,ListNode tail) {

        if (head.next == tail) {

            return head;
        }


        ListNode mid = findMid(head, tail);

        ListNode firstHead = divide(head,mid);
        ListNode secondHead = divide(mid, tail);


        ListNode dummp = new ListNode();
        ListNode tmpTail = dummp;

        while (firstHead != mid || secondHead != tail) {

            if ((firstHead == mid) ||
                    (secondHead != tail && firstHead.val > secondHead.val)) {

                tmpTail.next = secondHead;
                tmpTail = secondHead;
                secondHead = secondHead.next;
            }else if (firstHead != mid){

                tmpTail.next = firstHead;
                tmpTail = firstHead;
                firstHead = firstHead.next;
            }
        }

        tmpTail.next = tail;
        return dummp.next;
    }

    /**
     * 快慢指针
     */
    private ListNode findMid(ListNode head,ListNode tail) {

        // slow和fast都从起点开始
        ListNode slow = head;
        ListNode fast = head;

        while (fast != tail && fast != null && fast.next != null) {

            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {

                fast = fast.next;
            }
        }


        return slow;
    }

    public static void main(String[] args) {


        ListNode root = ListNode.general(new int[]{4,19,14,5,-3,1,8,5,11,15});

        _148_排序链表_归并排序 sortList = new _148_排序链表_归并排序();

        ListNode sortRoot = sortList.sortList(root);

        System.out.println(sortRoot);
    }
}
